#include<iostream>
using namespace std;
// assume f(a)*f(b) > 0
// tail recur version

/*
template<typename t>
double bisearch_rootfinding(t f, double a, double b, double tol = 1e-5)
{
    auto mid = (a+b)/2;
    if(b-a < tol) return mid;
    return f(a)*f(mid) < 0 ? bisearch_rootfinding(f,a,mid):bisearch_rootfinding(f,mid,b);
}
*/
// rewrite in while version
template<typename T>
double bisearch_rootfinding(T f, double a, double b, double TOL = 1e-5)
{
    auto mid = (a+b)/2;
    while(b-a > TOL)
    {
        if(f(a)*f(mid) < 0) b = mid;
        else a = mid;
        mid = (a+b)/2;
    }
    return mid;
}

int main(int argc, char const *argv[])
{
    auto res = bisearch_rootfinding([](auto x){return x*x-2;}, 0.5, 2);
    cout<<res<<"\n";
    return 0;
}
